🧩 核心思路

图模型 — Floyd-Warshall 全源最短路径 将 26 个小写字母视为图中的节点，字符转换视为带权有向边。通过 Floyd-Warshall 预处理出任意两个字符之间的最小转换成本，再遍历 source 的每个位置累加即可。

---

🔧 解题步骤

1. 初始化 26×26 的距离矩阵，对角线为 0，其余为正无穷
2. 遍历 original / changed / cost，建图（重复边取最小 cost）
3. Floyd-Warshall 三重循环求任意两字符间的最短路径
4. 遍历 source 的每一位，若 source[i] === target[i] 则跳过
5. 查表累加 dist[a][b]，若为 INF 则返回 -1
6. 返回总成本

---

⚠️ 关键点 / 易错点

• 建图时多条相同起止点的边要取 min（Math.min(dist[u][v], cost[i])）
• Floyd 内层需先判断 dist[i][k] 和 dist[k][j] 是否可达，否则 INF 相加会溢出
• 字符到索引的映射统一用 charCodeAt(0) - 97

---

🧪 复杂度

• 时间复杂度：O(26³ + n) ≈ O(n)，其中 n 为字符串长度，26³ 为常数
• 空间复杂度：O(26²) = O(1)

---

💻 代码

function minimumCost(
  source: string,
  target: string,
  original: string[],
  changed: string[],
  cost: number[],
): number {
  const N = 26;
  const INF = Infinity;

  // 1. 初始化图
  const dist = Array.from({ length: N }, () => new Array(N).fill(INF));
  for (let i = 0; i < N; i++) {
    dist[i][i] = 0;
  }

  // 2. 建边（取最小值）
  for (let i = 0; i < original.length; i++) {
    const u = original[i].charCodeAt(0) - 97;
    const v = changed[i].charCodeAt(0) - 97;
    dist[u][v] = Math.min(dist[u][v], cost[i]);
  }

  // 3. Floyd - 最短路径
  for (let k = 0; k < N; k++) {
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (dist[i][k] !== INF && dist[k][j] !== INF) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // 4. 计算 source -> target
  let ans = 0;
  for (let i = 0; i < source.length; i++) {
    const a = source[i].charCodeAt(0) - 97;
    const b = target[i].charCodeAt(0) - 97;
    if (a === b) continue;
    if (dist[a][b] === INF) return -1;
    ans += dist[a][b];
  }

  return ans;
}